package exercise02;

import java.util.*;

// 三数之和
// 重点: 去重
public class Day230706 {
    // 1. 暴力解法
    // 先排序数组 (从左往右遍历出三元组, 方便去重)
    // 枚举所有的三元组, 进行判断
    // 符合规则的三元组, 加入 set 中去重
    // 时间复杂度: O(n3)
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        Set<List<Integer>> ret = new HashSet<>();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[k]);
                        ret.add(list);
                    }
                }
            }
        }
        return new ArrayList<>(ret);
    }


    // 2. 使用双指针算法优化
    // 数组有序后, 要想到双指针和二分算法
    // 先固定一个数, 在用双指针在区间内查找两个数, 三个数之和为 0

    // 去重: 不使用容器去重,
    // 因为数组有序, 所以在找到一个结果后, 跳过重复的数, 就不会有重复了
    // 固定数一个数时, 要跳过重复的数, 双指针找到结果后, 也要跳过重复的数

    // 时间复杂度: O(n2)
    // 空间复杂度: 使用了快排
    public List<List<Integer>> threeSum2(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> ret = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            // 固定下一个数时, 跳过重复的数
            while (i > 0 && i < n && nums[i] == nums[i - 1]) {
                i++;
            }
            if (i >= n || nums[i] > 0) {
                // 小优化: 固定的这个数必须小于零(数组有序), 后面的数加起来才能等于零
                break;
            }

            // 双指针算法
            int left = i + 1;
            int right = n - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    ret.add(list);
                    // 找到一种结果之后, 缩小区间继续寻找
                    // 跳过重复的数进行去重
                    do {
                        left++;
                    } while (left < right && nums[left] == nums[left - 1]);
                    do {
                        right--;
                    } while (left < right && nums[right] == nums[right + 1]);
                } else if (sum > 0) {
                    right--;
                } else {
                    left++;
                }
            }
        }
        return ret;
    }
}

// 四数之和
// 不能小优化, 因为于三数之和不同, 不是等于零
// 要等于一个不确定的数 target
// 这个数可能为负数
// target = -11     [-5, -4, -2, 0, 1, 2]
// -5 -4 -2 0
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> ret = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            // 先固定一个数 a,
            // 然后在 a 后面的区间中, 找三数之和等于 target - a

            // 去重: 跳过重复的数
            while (i > 0 && i < n && nums[i] == nums[i - 1]) i++;

            for (int j = i + 1; j < n; j++) {
                // 再固定一个数 b
                // 然后用双指针算法, 在 b 后面的区间中. 找 两数之和等于 target - a - b

                // 去重: 跳过重复的数
                while (j > i + 1 && j < n && nums[j] == nums[j - 1]) j++;

                int left = j + 1;
                int right = n - 1;
                while (left < right) {
                    long sum = (long)nums[left] + nums[right] + nums[i] + nums[j];
                    if (sum < target) left++;
                    else if (sum > target) right--;
                    else {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[left]);
                        list.add(nums[right]);
                        ret.add(list);
                        // 找到一个结果, 缩小区间继续搜索
                        // 也要去重, 跳过重复的数
                        do {
                            left++;
                        } while (left < right && nums[left] == nums[left - 1]);
                        do {
                            right--;
                        } while (left < right && nums[right] == nums[right + 1]);
                    }
                }
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        new Solution().fourSum(new int[]{1000000000,1000000000,1000000000,1000000000}, -294967296);
    }
}
